package com.cheng.algorithm.sort;

import java.util.Arrays;

/**
 * @User Administrator
 * @Classname RadixSort
 * @Project Data-structure-and-algorithm
 * @Description 基数排序：
 * 基数排序(radix sort）属于“分配式排序”( distribution sort），又称“桶子法”(bucket sort）或bin sort，
 * 顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶（一维数组）”中，达到排序的作用
 * 实现:将整数按位数切割成不同的数字，然后按每个位数分别比较。
 * @Author wpcheng
 * @Create 2021-08-10-8:56
 * @Version 1.0
 */
public class RadixSort {
    public static void main(String[] args) {
        int arr[] = {53, 3, 542, 748, 14, 214};
        radixSort(arr);

    }

    public static void radixSort(int[] arr){
        /*根据最大数的为数来确定有几轮排序
        * 创建一个二维数组int[10][arr.length]：
        * 10表示10个一维数组，也就是10个桶，分别为0-9;arr.length表示每个桶可以存放数的最大个数
        * 对每个数的个位数进行排序后，按个位数大小分别放入与下标对应的桶
        * */
        int[][] bucket = new int[10][arr.length];
        //记录每个桶放了多少个数,如bucketElementCounts[1] 放的就是下标为1的桶里数的个数
        int[] bucketElementCounts = new int[10];
        //第一轮，对每个数的个位数进行排序
        for (int j = 0; j < arr.length; j++) {
            //得到每个数的个位数
            int digitOfElement = arr[j] % 10;
            //根据个位数放入对应的桶 [digitOfElement]表示放入第几个桶，[bucketElementCounts[digitOfElement]]表示当前桶存放数的个数
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            bucketElementCounts[digitOfElement]++;
        }
        //把桶里的数放回数组
        int index = 0;
        //循环所有的桶
        for (int k = 0; k < bucketElementCounts.length; k++) {
            if (bucketElementCounts[k] != 0){
                //循环第k个桶
                for (int l = 0; l < bucketElementCounts[k]; l++) {
                    arr[index] = bucket[k][l];
                    index++;
                }
            }
            //每循环完一个桶，就把该桶置为0
            bucketElementCounts[k] = 0;
        }
        System.out.println(Arrays.toString(arr));

        //第二轮，对每个数的十位数进行排序
        for (int j = 0; j < arr.length; j++) {
            //得到每个数的十位数
            int digitOfElement = arr[j] /10 % 10;
            //根据个位数放入对应的桶 [digitOfElement]表示放入第几个桶，[bucketElementCounts[digitOfElement]]表示当前桶存放数的个数
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            bucketElementCounts[digitOfElement]++;
        }
        index = 0;
        //把桶里的数放回数组
        //循环所有的桶
        for (int k = 0; k < bucketElementCounts.length; k++) {
            if (bucketElementCounts[k] != 0){
                //循环第k个桶
                for (int l = 0; l < bucketElementCounts[k]; l++) {
                    arr[index] = bucket[k][l];
                    index++;
                }
            }
            //每循环完一个桶，就把该桶置为0
            bucketElementCounts[k] = 0;

        }
        System.out.println(Arrays.toString(arr));

        //第三轮，对每个数的百位数进行排序
        for (int j = 0; j < arr.length; j++) {
            //得到每个数的百位数
            int digitOfElement = arr[j] /100 % 10;
            //根据个位数放入对应的桶 [digitOfElement]表示放入第几个桶，[bucketElementCounts[digitOfElement]]表示当前桶存放数的个数
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            bucketElementCounts[digitOfElement]++;
        }
        index = 0;
        //把桶里的数放回数组
        //循环所有的桶
        for (int k = 0; k < bucketElementCounts.length; k++) {
            if (bucketElementCounts[k] != 0){
                //循环第k个桶
                for (int l = 0; l < bucketElementCounts[k]; l++) {
                    arr[index] = bucket[k][l];
                    index++;
                }
            }
            //每循环完一个桶，就把该桶置为0
            bucketElementCounts[k] = 0;

        }
        System.out.println(Arrays.toString(arr));
    }
}
